1. The Field of the Invention
The present invention relates to public key cryptosystems, and more particularly to a method for designing public key cryptosystems against fault-based attacks since protection of the secret information stored in a tamperproof device is very important to an electronic cash system. A new fault-resistant method and system for countering information leakage to resist both the memory and computational fault-based attacks has been developed. The fault-resistant system can be readily implemented in public key cryptosystems and will achieve a high performance in computation.
2. Description of the Related Art
A smart card, which involves public-key or secret-key cryptosystems in a tamperproof device to ensure the security, is held as an important invention to provide people with a more convenient life style. The security of the public-key based smart card systems depends on the supposed difficulty of a factorization or discrete logarithm problem. For a tamperfree device, however, the secret information stored in a memory or register may induce random transient faults due to the attacks by applying stress, electromagnetic waves, ionization, etc. The transient faults can be further divided into memory faults and computational faults, and those attacks, which are called memory and computational fault-based attacks, break various public-key cryptosystems by taking the advantage of random hardware faults, and so endanger many network security products and systems.
A memory fault denotes an original information bit stored in the memory or register spontaneously changed from 1 to 0, or vice versa. In this case, there is no additional information obtained from the error to attack the cryptosystem. This is because the system now behaves like the one with a different secret key.
Furthermore, some secret information may be revealed by using the faulty output if the stored secret key is correct but is randomly caused to become faulty when it was fetched from the memory. However, if the information is verified successfully after it is fetched from the memory, the memory fault attack can be prevented.
A computational fault indicates that a fault is generated during a cryptographic computation. Since a processor must access the memory and perform the cryptographic computation frequently, the computational fault may occur with a higher probability than the memory fault.
One computational fault-based attack on an RSA public-key cryptosystem is described as follows. Let N=pq and e.multidot.d=1 (mod .Yen.(N)), where p and q are large primes, (e,N) and d are public and secret keys, respectively; and .Yen.(.multidot.) is the Euler totient function. For an RSA digital signature s=m.sup.d (mod N), s.sub.p =m.sup.d (mod p) and s.sub.q =m.sup.d (mod q) are first computed and the signature s is subsequently obtained by using the Chinese Remainder Theory (CRT), that is, s=crt (N,p,q,s.sub.p,s.sub.q).
However, the result of the cryptographic computation may be erroneous due to the computational fault. Let s.sub.p ' be a faulty partial signature, and s.sub.q be an error-free one, then a faulty signature is s'=crt(N,p,q,s.sub.p ',s.sub.q). If an attacker obtains a message m and the faulty signature s', a prime q can be successfully obtained by computing q=GCD((s').sup.e -m,N), where GCD denotes the greatest common divisor. Thus, the RSA cryptosystem will be completely broken by using one computational fault only.
Conventional countermeasures such as recomputations and verifications, or random padding, etc. are used to resist the fault-based attacks. However, those conventional methods still have some disadvantages with respect to computational complexity.
In order to detect faults in a tamperproof device during the cryptographic computation, it is necessary to develop an efficient computation system with an error-checking ability. On public-key cryptosystems, a structure of a fault-resistant system (FRS) which is a public system being capable to detect any fault existing in modular multiplication with very high probability as well as a concrete implementation of the FRS for the RSA system are set forth as follows. This fault-resistant RSA system can also resist the memory fault-based attacks and can be readily applied to other public-key cryptosystems with the same algebraic structure.